﻿namespace ContentHolder
{
    public sealed class SingleKeywordMatcher : IKeywordMatcher
    {
        private readonly ushort[] _dict;
        private readonly int[] _first;
        private readonly IntDictionary[] _nextIndex;
        private readonly int[] _end;
        private readonly int[] _resultIndex;
        private readonly int[] _keywordLengths;

        public SingleKeywordMatcher(IEnumerable<string> keywords)
        {
            this._keywordLengths = GenerateKeywordLength(keywords);
            var root = new TrieNode();
            var allNode = GenerateAllNodes(keywords, root);
            root.Failure = root;
            this._dict = GenerateDict(allNode);
            this._first = GenerateFirst(allNode);
            this._nextIndex = GenerateIndexs(allNode, root, out var resultIndex2, out var isEndStart);

            var (ResultIndex, End) = GenerateResultIndex(resultIndex2, isEndStart);
            this._resultIndex = ResultIndex;
            this._end = End;
        }
        private static int[] GenerateKeywordLength(IEnumerable<string> source)
        {
            var lengths = new int[source.Count()];
            int index = 0;
            foreach (var item in source)
            {
                lengths[index++] = item.Length;
            }

            return lengths;
        }

        #region 解析关键词列表 ==> Node

        private static List<TrieNode> GenerateAllNodes(IEnumerable<string> keywords, TrieNode root)
        {
            var allNodeLayers = ParseNodeLayers(keywords, root);

            var allNode = allNodeLayers.Values.SelectMany(n => n).ToList();
            allNode.Insert(0, root);

            for (int i = 1; i < allNode.Count; i++)
            {
                SetNode(allNode[i], i, root);
            }
            return allNode;
        }
        private static void SetNode(TrieNode nd, int i, TrieNode root)
        {
            nd.Index = i;
            TrieNode? r = nd.Parent?.Failure;
            char c = nd.Char;
            while (r != default && !r.m_values.ContainsKey(c))
            {
                r = r.Failure;
            }

            nd.Failure = r == default ? root : r.m_values[c];
            foreach (var result in nd.Failure.Results ?? [])
            {
                nd.SetResults(result);
            }
        }
        static Dictionary<int, List<TrieNode>> ParseNodeLayers(IEnumerable<string> keywords, TrieNode root)
        {
            // 所有节点页
            var allNodeLayers = new Dictionary<int, List<TrieNode>>();
            int index = 0;
            foreach (var keyword in keywords)
            {
                // 每一个关键词都先从根节点开始
                var node = root;
                // 解析单个关键词
                ParseSingleKeyword(keyword, node, allNodeLayers);
                // 设置最后一个节点
                node.SetResults(index++);
            }

            return allNodeLayers;
        }
        static void ParseSingleKeyword(string keyword, TrieNode node, Dictionary<int, List<TrieNode>> nodeLayerMap)
        {
            var keywordSpan = keyword.AsSpan();
            for (int j = 0; j < keywordSpan.Length; j++)
            {
                // 在上一级节点上添加子节点（内部是一个字典），相当于这个节点有多少偏子叶
                node = node.Add(keywordSpan[j]);

                // 判断是否为新节点
                if (node.Layer != 0)
                {
                    continue;
                }

                node.Layer = j + 1;
                if (!nodeLayerMap.TryGetValue(node.Layer, out var trieNodes))
                {
                    trieNodes = new List<TrieNode>();
                    nodeLayerMap[node.Layer] = trieNodes;
                }
                trieNodes.Add(node);
            }
        }

        #endregion

        private static (int[] ResultIndex, int[] End) GenerateResultIndex(List<int> resultIndex2, List<bool> isEndStart)
        {
            var resultIndex = new List<int>();
            var end = new List<int>() { };
            for (int i = isEndStart.Count - 1; i >= 0; i--)
            {
                if (isEndStart[i])
                {
                    end.Add(resultIndex.Count);
                }
                if (resultIndex2[i] > -1)
                {
                    resultIndex.Add(resultIndex2[i]);
                }
            }
            end.Add(resultIndex.Count);

            return (resultIndex.ToArray(), end.ToArray());
        }
        private IntDictionary[] GenerateIndexs(List<TrieNode> allNodes, TrieNode root, out List<int> resultIndex2, out List<bool> isEndStart)
        {
            resultIndex2 = new List<int>();
            isEndStart = new List<bool>();
            var _nextIndex2 = new IntDictionary[allNodes.Count];

            for (int i = allNodes.Count - 1; i >= 0; i--)
            {
                var dict = new Dictionary<ushort, int>();
                var result = new List<int>();
                var oldNode = allNodes[i];

                if (oldNode.m_values != null)
                {
                    foreach (var item in oldNode.m_values)
                    {
                        var key = (char)this._dict[item.Key];
                        var index = item.Value.Index;
                        dict[key] = index;
                    }
                }
                if (oldNode.Results != null)
                {
                    foreach (var item in oldNode.Results)
                    {
                        if (result.Contains(item) == false)
                        {
                            result.Add(item);
                        }
                    }
                }

                oldNode = oldNode.Failure;
                while (oldNode != root)
                {
                    if (oldNode?.m_values != null)
                    {
                        foreach (var item in oldNode.m_values)
                        {
                            var key = (char)_dict[item.Key];
                            var index = item.Value.Index;
                            if (dict.ContainsKey(key) == false)
                            {
                                dict[key] = index;
                            }
                        }
                    }
                    if (oldNode?.Results != null)
                    {
                        foreach (var item in oldNode.Results)
                        {
                            if (result.Contains(item) == false)
                            {
                                result.Add(item);
                            }
                        }
                    }
                    oldNode = oldNode?.Failure;
                }
                _nextIndex2[i] = new IntDictionary(dict);

                if (result.Count > 0)
                {
                    for (int j = result.Count - 1; j >= 0; j--)
                    {
                        resultIndex2.Add(result[j]);
                        isEndStart.Add(false);
                    }
                    isEndStart[isEndStart.Count - 1] = true;
                }
                else
                {
                    resultIndex2.Add(-1);
                    isEndStart.Add(true);
                }
                dict = null;
                result = null;
                allNodes[i].Dispose();
                allNodes.RemoveAt(i);
            }
            return _nextIndex2;
        }
        private int[] GenerateFirst(List<TrieNode> allNodes)
        {
            var first = new int[char.MaxValue + 1];
            foreach (var item in allNodes[0].m_values ?? new Dictionary<char, TrieNode>())
            {
                var key = (char)_dict[item.Key];
                first[key] = item.Value.Index;
            }
            return first;
        }
        private static ushort[] GenerateDict(List<TrieNode> allNodes)
        {
            var keywords = string.Concat(allNodes.Skip(1).Select(n => n.Char));

            var dictionary = SumKeywordCount(keywords);

            var list = ParseCharList(dictionary);

            var dict = new ushort[char.MaxValue + 1];
            for (int i = 0; i < list.Count; i++)
            {
                dict[list[i]] = (ushort)(i + 1);
            }

            return dict;
        }
        private static IDictionary<char, int> SumKeywordCount(string keywords)
        {
            var dictionary = new Dictionary<char, int>();
            foreach (var item in keywords)
            {
                if (dictionary.ContainsKey(item))
                {
                    dictionary[item] += 1;
                }
                else
                {
                    dictionary[item] = 1;
                }
            }
            return dictionary;
        }
        private static IList<char> ParseCharList(IDictionary<char, int> dictionary)
        {
            var list = new List<char>();
            var flag = false;
            foreach (var item in dictionary.OrderByDescending(q => q.Value).Select(q => q.Key))
            {
                if (flag)
                {
                    list.Add(item);
                }
                else
                {
                    list.Insert(0, item);
                }
                flag = !flag;
            }
            return list;
        }
        public IEnumerable<string> Matching(string source)
        {
            var result = new List<string>();
            var p = 0;
            var sourceSpans = source.AsSpan();
            for (int i = 0; i < sourceSpans.Length; i++)
            {
                var t = _dict[sourceSpans[i]];

                if (t == 0)
                {
                    p = 0;
                    continue;
                }

                if (p == 0 || _nextIndex[p].TryGetValue(t, out int next) == false)
                {
                    next = _first[t];
                }

                if (next != 0)
                {
                    for (int j = _end[next]; j < _end[next + 1]; j++)
                    {
                        var index = _resultIndex[j];
                        var len = _keywordLengths[index];
                        var key = sourceSpans.Slice(i + 1 - len, len).ToString();
                        result.Add(key);
                    }
                }

                p = next;
            }
            return result;
        }
    }
}
